
/**
 * 
 * 最佳植树距离
 * 
 * 题目描述

按照环保公司要求，小明需要在沙化严重的地区进行植树防沙工作，初步目标是种植一条直线的树带。由于有些区域目前不适合种植树木，所以只能在一些可以种植的点来种植树木。

在树苗有限的情况下，要达到最佳效果，就要尽量散开种植，不同树苗之间的最小间距要尽量大。给你一个适合种情树木的点坐标和一个树苗的数量，请帮小明选择一个最佳的最小种植间距。

例如，适合种植树木的位置分别为1,3,5,6,7,10,13 树苗数量是3，种植位置在1,7,13，树苗之间的间距都是6，均匀分开，就达到了散开种植的目的，最佳的最小种植间距是6

输入描述
第 1 行表示：适合种树的坐标数量
第 2 行表示：适合种树的坐标位置
第 3 行表示：树苗的数量


例如：

7
1 5 3 6 10 7 13
3
输出描述
最佳的最小种植间距

备注
位置范围为1~10000000
种植树苗的数量范围2~10000000
用例确保种桔的树苗数量不会超过有效种桔坐标数量
用例
输入	7
1 5 3 6 10 7 13
3
输出	6
说明	3棵树苗分别种植在1，7，13位置时，树苗种植的最均匀，最小间距为6

 */

import java.util.Arrays;
import java.util.Scanner;

/**
  * 
  题目解析
本题是LeetCode - 1552 两球之间的磁力_伏城之外的博客-CSDN博客

二分法


的换皮题。题解请参考链接博客。
  */
public class 最佳植树距离 {

    static int n, m;
    static int[] positions;

    
    public static void main(String[] args) {
        
       Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
 
        positions = new int[n];
        for (int i = 0; i < n; i++) {
            positions[i] = sc.nextInt();
        }
 
        m = sc.nextInt();
 
        // 核心代码
        Arrays.sort(positions);
 
        int min = 1;
        int max = positions[n - 1] - positions[0];
 
        int ans = 0;
        while (min <= max) {
            int mid = (min + max) / 2;
 
            if (check(mid)) {
                ans = mid;
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
 
        System.out.println(ans);
    }
 
    public static boolean check(int minDis) {
        int count = 1;
 
        int last = 0;
        for (int cur = 1; cur < n; cur++) {
            if (positions[cur] - positions[last] >= minDis) {
                count++;
                last = cur;
            }
        }
 
        return count >= m;
    }

}
